#include <bits/stdc++.h>

using namespace std;

const int	N=110000;

int	n,m,a[N];
int	visited[N],BIT1[N],BIT2[N];

int	BLOCK_SIZE;

struct query
{
	int	l,r,x,y,pos,block;
	query() {} 
	query(const int ar1,const int ar2,const int ar3,const int ar4,const int ar5):
		l(ar1),r(ar2),x(ar3),y(ar4),pos(ar5),block(l/BLOCK_SIZE){}
	bool	operator<(const query temp)const
	{
		if(block!=temp.block)return block<temp.block;
		return r<temp.r;
	}
}Q[1100000];

void	Add1(const int x) { for(register int i=x;i<=n;i+=i&-i)BIT1[i]++; }
void	Remove1(const int x) { for(register int i=x;i<=n;i+=i&-i)BIT1[i]--; }
int	Query1(const int x) { int temp=0; for(register int i=x;i;i-=i&-i)temp+=BIT1[i]; return temp; }
int	Query1(const int x,const int y) { return Query1(y)-Query1(x-1); }
void	Add2(const int x) { for(register int i=x;i<=n;i+=i&-i)BIT2[i]++; }
void	Remove2(const int x) { for(register int i=x;i<=n;i+=i&-i)BIT2[i]--; }
int	Query2(const int x) { int temp=0; for(register int i=x;i;i-=i&-i)temp+=BIT2[i]; return temp; }
int	Query2(const int x,const int y) { return Query2(y)-Query2(x-1); }

pair<int,int> Ans[1100000];

int main()
{
	int	i,x,y,l,r; vector<int>vec; vec.resize(110000);
	scanf("%d%d",&n,&m); BLOCK_SIZE=(int)sqrt(n);
	for(i=1;i<=n;++i)scanf("%d",&a[i]),vec.push_back(a[i]),vec.push_back(a[i]-1),
		vec.push_back(a[i]+1);
	vec.push_back(0); sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	for(i=0;i<=n;++i)a[i]=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()+1;
	for(i=1;i<=m;++i)
	{
		scanf("%d%d%d%d",&l,&r,&x,&y);
		x=lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1;
		y=lower_bound(vec.begin(),vec.end(),y)-vec.begin()+1;
		Q[i]=query(l,r,x,y,i);
	}
	sort(Q+1,Q+m+1); l=0,r=0;
	for(i=1;i<=m;++i)
	{
		while(r<Q[i].r)
		{
			r++;
			visited[a[r]]++;
			if(visited[a[r]]==1)Add1(a[r]);
			Add2(a[r]);
		}
		while(r>Q[i].r)
		{
			visited[a[r]]--;
			if(visited[a[r]]==0)Remove1(a[r]);
			Remove2(a[r]);
			r--;
		}
		while(l<Q[i].l)
		{
			visited[a[l]]--;
			if(visited[a[l]]==0)Remove1(a[l]);
			Remove2(a[l]);
			l++;
		}
		while(l>Q[i].l)
		{
			l--;
			visited[a[l]]++;
			if(visited[a[l]]==1)Add1(a[l]);
			Add2(a[l]);
		}
		Ans[Q[i].pos].second=Query1(Q[i].x,Q[i].y);
		Ans[Q[i].pos].first=Query2(Q[i].x,Q[i].y);
	}
	for(i=1;i<=m;++i)
		printf("%d %d\n",Ans[i].first,Ans[i].second);
	return 0;
}
